/*
  (C) 2005 - Boston University
  		Adam D. Bradley and Michael Ocean
  Contact: Michael Ocean 

  This work is a part of the larger snBench project.  Information
  can be found at: http://csr.bu.edu/snbench 

  This program is free software; you can redistribute it and/or
  modify it under the terms of Version 2 of the GNU General Public 
  License.
  
  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  General Public License for more details.
  
  You should have received a copy of the GNU Library General Public
  License along with this library; if not, write to the Free
  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

package step;

import java.awt.Dimension;
import java.io.ByteArrayOutputStream;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.net.URI;
import java.net.URISyntaxException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.locks.ReentrantReadWriteLock;

import javax.swing.JFrame;
import javax.swing.JTabbedPane;

import snbenchlib.IDManagedHashTable;
import snbenchlib.Log;
import snbenchlib.Trace;
import snbenchlib.UID;
import stepide.STEPVisualizer.JStepPanel;
import sxe.SxeMonitor;

public class Graph
{
	//private Node nodes[];
	private String ID;
	private IDManagedHashTable<Node> htNodes;
	
	private boolean bAsleep = false;
	private boolean splices_resolved = false;
	private boolean normalized = false;
	private boolean bound = false;
	
	private Iterator<Node> iterator = null;
	private boolean something_done_this_pass = false;

	/**
	 * SJJ - SMOD
	 * Added ReentrantReadWriteLock to implement readers/writers
	 * exclusion on the graph and its nodes
	 */
	private ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
	
	
	public static Graph newEmptyGraph(String id) {
		return new Graph(id);
	}

	public static Graph newEmptyGraph() {
		return new Graph(String.valueOf((new java.util.Date()).getTime()));
	}

	/**
	 * protected -- use static method newEmptyGraph instead
	 * @param _id
	 */
	protected Graph(String _id) {
		iterator = null;
		ID = _id;
		htNodes = new IDManagedHashTable<Node>();
		
	}
	
	/**
	 * Ensure that LAST_TRIGGER_EVALs are
	 * properly linked to their targets
	 * (and not dangling)
	 */
	public void Normalize() throws DanglingSplice{
		Node n = null;
		Iterator<Node> it = htNodes.Values().iterator();
        while (it.hasNext()) { 
        	n = it.next();
        	
        	if(n.IsOrphan()){
        		n.Normalize(this);
			}
		}
		normalized = true;
	}

	/* Binding establishes the correct node URI for
	 * every node and, in the case of ExpNodes, also
	 * allocates the Opcode for this node.  If the
	 * class can not be found (and can not be loaded
	 * dynamically) in this case the admission should 
	 * fail, so we return false.
	 */
	public void Bind() throws ClassNotFoundException {
		Node n = null;
		Iterator<Node> it = htNodes.Values().iterator();
        while (it.hasNext()) { 
        	n = it.next();
			/* will throw ClassNotFound if Opcode 
			 * can't be resolved */
			n.Bind();
		}
		bound = true;
	}

	/* Handles all splices
	 * 
	 * Caller *must* have lock!
	 */
	public void ResolveSplices() throws DanglingSplice {
		assert(this.isWriteLockedByCurrentThread());

		Node n = null;
		Iterator<Node> it = htNodes.Values().iterator();
        while (it.hasNext()) { 
        	n = it.next();

			if (n instanceof SpliceNode) {
				ResolveSplice((SpliceNode)n);
			}
		}

		it = htNodes.Values().iterator();
        while (it.hasNext()) { 
        	n = it.next();
        	
			if(n instanceof SpliceNode)
				it.remove();
			
		}

		splices_resolved = true;
	}

	/* Handles a splice at the given point.
	 * 
	 * Caller *must* have lock!
	 */
	@Deprecated
	private void ResolveSpliceOld(step.Node nSplicePoint) throws DanglingSplice {
		assert(this.isWriteLockedByCurrentThread());
		
		/* make sure this node is actually in the graph... 
		AddNode(nSplicePoint); 
		
		for (int i=0 ; i<nodes.length ; i++) {
			if (nodes[i] == nSplicePoint) {
				ResolveSplice(i);
				return;
			}
		}
		assert(false);
		*/
	}
	
	/* 
	 * Replace the links to and from the node nSplicePoint with the
	 * node that the splice node points to (attribute target=<targetID>)
	 * 
	 * nSplicePoint is not deleted from the node collection of the graph,  
	 * Caller should delete it otherwise it hangs useless in the ID space.
	 * 
	 * Caller *must* have lock!
	 */
	private void ResolveSplice(SpliceNode nSplicePoint) throws DanglingSplice {
		assert(this.isWriteLockedByCurrentThread());

		/* The SpliceNode (RefNode in the white paper) is the 
		 * mechanism for encoding a DAG as a tree (XML),
		 * necessary for supporting let-binding.
		 * It also is used to specify how a delta-graph is 
		 * connected to a base graph. */

		Node nTarget = GetNode(nSplicePoint.GetTarget());
		if (nTarget==null) {
			throw new DanglingSplice(this, nSplicePoint);
		}

		/* DEBUG stuff...
		System.err.println("Attempting to resolve a SpliceNode:");
		System.err.println("  Splice children:");
		for (int i=0 ; i<nSplicePoint.children.length ; i++)
			System.err.println("  - ID : " + nSplicePoint.children[i].GetID());
		System.err.println("  Splice parents:");
		for (int i=0 ; i<nSplicePoint.parents.length ; i++)
			System.err.println("  - ID : " + nSplicePoint.parents[i].GetID());
		System.err.println("  Target children:");
		for (int i=0 ; i<nTarget.children.length ; i++)
			System.err.println("  - ID : " + nTarget.children[i].GetID());
		System.err.println("  Target parents:");
		for (int i=0 ; i<nTarget.children.length ; i++)
			System.err.println("  - ID : " + nTarget.parents[i].GetID());
		*/

		/* 
		 * This gets subtle.
		 * 
		 * We need to update mutual references between the 
		 * target node and its parents/children, following the
		 * whitepaper's rules.
		 * 
		 * First, re-target the SpliceNode's parents to the Target.
		 */
		assert(this.isWriteLockedByCurrentThread());
		nSplicePoint.graft_RedirectParentsToNode(nTarget);
		/*
		 * Second, add the SpliceNode's parents to Target.parents[].
		 */
		for (int i=0 ; i<nSplicePoint.parents.length ; i++) {
			nTarget.AddParent(nSplicePoint.parents[i]);
		}
		
		/* 
		 * Third, re-target the SpliceNode's children to the Target.
		 */
		assert(this.isWriteLockedByCurrentThread());
		nSplicePoint.graft_RedirectChildrenToNode(nTarget);
		/*
		 * --- This is the tricky one --- 
		 * Last, if the SpliceNode has children, replace Target's 
		 * children with them.  Otherwise, leave 'em be.
		 */
		if (nSplicePoint.children.length > 0)
			nTarget.children = nSplicePoint.children;

		/* 
		 * No need to keep the SpliceNode around, it's transitory.
		 * Kill the reference immediately, skip the garbage 
		 * collector, do not pass go, do not collect $200.
		 */
		nSplicePoint.cleanup();

		//RemoveNode(nSplicePoint);

		/* DEBUG stuff
		System.err.println("SpliceNode Resolution Result:");
		System.err.println("  Target children:");
		for (int i=0 ; i<nTarget.children.length ; i++)
			System.err.println("  - ID : " + nTarget.children[i].GetID());
		System.err.println("  Target parents:");
		for (int i=0 ; i<nTarget.children.length ; i++)
			System.err.println("  - ID : " + nTarget.parents[i].GetID());

		System.err.println("End of report");
		*/
		
	}

	private void ReplaceSplices(){
		Node n = null;
		Iterator<Node> it = htNodes.Values().iterator();
        while (it.hasNext()) { 
        	n = it.next();

			if(n.parents.length >1){
				// redirect all parents except first to new splices
				for (int i=1 ; i<n.parents.length ; i++) {
					Node nTmp = n.parents[i];
					for(int j=0;j<nTmp.children.length;j++){
						if(nTmp.children[j] == n) {
							SpliceNode sn = new SpliceNode(n.GetID());
							nTmp.children[j]=sn;
							sn.AddParent(nTmp);
						}
					}
				}
				// shrink parents of the one "real" node accordingly
				n.parents = new Node[1];
				n.parents[0] = n;
			}
		}
	}
	
	synchronized public void kill_iterator(){
		System.out.println("kill_iterator called");
		if(bAsleep){
			System.out.println("kill_iterator:asleep!  Waking...");
			notify();
		}
	}
	
    synchronized public boolean iterate()
    {
	    assert(splices_resolved);
	    assert(normalized);
	    assert(bound);

		boolean ret = false;

		Node n = null;
		/*
		Iterator<Node> it = htNodes.Values().iterator();
        while (it.hasNext()) { 
        	n = it.next();
		 */
		if(iterator==null){
			something_done_this_pass=false;
			iterator = htNodes.Values().iterator();
		}

		//if (nodes.length>0) {
		if (iterator.hasNext()) {
			n = iterator.next();
			Log.evaluator.log("Considering " + n.GetID() , Trace.VERBOSE);
		
			if (n.IsEnabled())
			{
				Log.evaluator.log(
						"--Evaluating node [" + n.GetID() + "]",
						Trace.HELP);
				try {
					n.DoEvaluate();
					ret = true;
					something_done_this_pass = true;
				} catch (EvaluationFailure ef) {
					/* DOME - report error to SD, put the failing node in a "dead" state */
					n.markAsGarbage();
					
					Log.evaluator.log("Evaluation failure for Node" + n.GetID() + " in Graph " + ID + 
							ef.getMessage(), Trace.MINIMAL);
					
					System.out.println("Evaluation failure! " + 
							   ef.getMessage());
					ef.printStackTrace();
					ret = false;
				}
			} else {
				ret = false;
			}
		}
		else{
			iterator = null;
		}
		
		if((iterator==null)&&(!something_done_this_pass))
		{
			/* indicates we should stop evaluating until
			 * something changes
			 */ 
			try{
				Log.evaluator.log(
						"Evaluation iterator going to sleep @ node " + iterator,
						Trace.MINIMAL);
				Log.evaluator.applyTimeStamp(Trace.MINIMAL);
				
				bAsleep = true;
				/* check for spurious wakeups */
				/* SJJ - SMOD: 0=indefinitely. According to the documentation, wait must be
				 enclosed in a cycle that checks the wait condition to catch spurious wakeups */
				wait(0);	
			} catch(InterruptedException ie){
				Log.evaluator.log("Iteration sleep interupted", Trace.HELP);
			}
			
			Log.evaluator.log("Evaluation iterator woken up", Trace.MINIMAL);
			Log.evaluator.applyTimeStamp(Trace.MINIMAL);
		}
		
		bAsleep = false;
				
		return ret;
    }

    synchronized public void restUntilGraft(){
    	try{
    		Log.evaluator.log("Iteration sleep induced", Trace.HELP);
    		bAsleep = true;
			/* check for spurious wakeups */
			/* SJJ - SMOD: 0=indefinitely. According to the documentation, wait must be
			 enclosed in a cycle that checks the wait condition to catch spurious wakeups */
			wait(0);	
		} catch(InterruptedException ie){
			Log.evaluator.log("Iteration sleep interupted", Trace.HELP);
		}    	
    }
    
    /** 
     * @return ID of node executed on this pass or null if no node is executed on this
     * 		pass 
     */
    
    synchronized public ArrayList<Node> getReadyNodes()
    {
	    assert(splices_resolved);
	    assert(normalized);
	    assert(bound);

	    Log.evaluator.log("getReadyNodes() began" , Trace.VERBOSE);
	    
	    getReadLock();
	    
    	iterator = htNodes.Values().iterator();
		
		int i = 0;
		int t = htNodes.Size();
		String sID = null;
		Node n = null;
		ArrayList<Node> al = new ArrayList<Node>();
		
		while (iterator.hasNext()) { 
			i++;
			n = iterator.next();
			sID = n.GetID();
			
			Log.evaluator.log("getReadyNodes Considering [" + i + "/" + t + "], id={" + sID + "}" , Trace.VERBOSE);
			
			if (n.IsEnabled())
			{
				Log.evaluator.log(
						"--getReadyNodes queuing node [" + sID + "]",
						Trace.HELP);
				al.add(n);
			}
		}
		releaseReadLock();
		
		return al;
    }

     /******/
	public void Write(String filename) {
		getReadLock();
		OutputStream os = null;
		try {
			os = new FileOutputStream(filename);
			try {
				os.write("<?xml version=\"1.0\"?>\n".getBytes());
				os.write(("<stepgraph id=\"" + ID + "\">\n").getBytes());
				
				Node n = null;
				Iterator<Node> it = htNodes.Values().iterator();
		        while (it.hasNext()) { 
		        	n = it.next();
		        	if(n.IsOrphan())
		        		n.Write(os, 1);
		        }
		        
				os.write("</stepgraph>\n".getBytes());
				os.write("<!-- generated by the snBench library reference implementation v0.0 -->\n".getBytes());
				os.close();
			} catch (java.io.IOException e) {
				System.err.println("I/O error: " + e.toString());
				System.exit(-1);
			}
		} catch (java.io.FileNotFoundException e) {
			System.err.println("Error: " + e.toString());
			System.exit(-1);
		}
		System.err.println("graph successfully written");
		releaseReadLock();
	}

    /* SJJ recommended change.
	public String Serialize() {
    	StringBuffer sb = new StringBuffer();
    	sb.append("<?xml version=\"1.0\"?>\n");
    	sb.append("<stepgraph id=\"" + ID + "\">\n");
    	int piter;
    	for (piter=0 ; piter<nodes.length ; piter++) {
    		if (nodes[piter].parents.length == 0) {
    			// make an output stream for a string 
    			ByteArrayOutputStream baos = new ByteArrayOutputStream();
    			try{
    				nodes[piter].Write(baos, 1);
    				sb.append(baos.toString());
    			}
    			catch(Exception e){
    				e.printStackTrace();
    			}
    		}
    	}
    	sb.append("</stepgraph>\n");
    	sb.append("<!-- generated by the snBench library reference implementation v0.0 -->\n");
    		
    	return sb.toString();
        }
	*/
	public String Serialize() {
		getReadLock();
		StringBuffer sb = new StringBuffer();
		sb.append("<?xml version=\"1.0\"?>\n");
		sb.append("<stepgraph id=\"" + ID + "\">\n");
		    	
		for (Node node: getRoots()) {
			ByteArrayOutputStream baos = new ByteArrayOutputStream();
			try{
				node.Write(baos, 1);
				sb.append(baos.toString());
			}
			catch(Exception e){
				e.printStackTrace();
			}
		}
		sb.append("</stepgraph>\n");
		sb.append("<!-- generated by the snBench library reference implementation v0.0 -->\n");
		releaseReadLock();
		return sb.toString();
	}
	
	public Node GetNode(String target_id) {
		Node n = htNodes.Get(new UID(target_id));
		return n;
	}

	public int GetNodes(){
		return htNodes.Size();
	}
	
	/**
	 * Be Cautious!!  this.AddNode() or this.RemoveNode()
	 * with an Iterator in use will generate an exception!  
	 *
	 * This is not mutable access to the Nodes of the graph.  
	 * Nodes added through this interface are fundamentally
	 * broken and results in a broken graph.  So don't iterator.add!
	 * 
	 * @return
	 */
	public Iterator<Node> GetNodeIterator() {
		return htNodes.Values().iterator();
	}

	/**
	 * This is unsafe direct access to the graph.
	 *
	 * @return
	 */
	public Collection<Node> GetAllNodes(){
		return htNodes.Values();
	}
	
	/**
	 * This function is used by sxe.GraphEvaluatorThread to determine
	 * whether the graph is "clear" for termination.  Basically, we
	 * don't want to terminate the graph if there are non-persistent
	 * queries whose evaluations are incomplete.
	 * 
	 * To test this, it is sufficient to find all of the non-trigger
	 * roots and check their "evaluated" flags.
	 */
	synchronized public boolean PendingTransientEvaluation() {
		Node n = null;
		Iterator<Node> it = htNodes.Values().iterator();
        while (it.hasNext()) { 
        	n = it.next();

			if ((n.parents.length == 0) && // a root
			    !(n instanceof LevelTriggerNode) && // not LT
			    !(n instanceof EdgeTriggerNode) && // not ET
			    !n.rt_evaluated) // not yet evaluated
				return true;
		}
		return false;
	}

	/**
	 * Note that the node itself is added to 
	 * the node list, but nodes to which it is linked (parents and 
	 * children) are not.  This is usually handled by the 
	 * Node.Realize() method.
	 * 
	 * Equiv to just adding the node to the underlying hashtable, except
	 * this method also sets the node's source graphID
	 * 		
	 *  caller better have the write lock...
	 *  
	 *  returns true if the node is added 
	 *  false if the node was already present
	 *  throws DuplicateID if the node could not be added
	 *  because a different node with the same ID was there
	 *  
	 */
	public boolean AddNode(Node n) throws DuplicateID{
		
		if (n.SourceGraphID == null)
			n.SourceGraphID = ID;
		
		//if(n.GetID()==null)
		//	throw new Exception("Node ID must be non-null!!" + n.GetInfoXML());
		
		UID uid = new UID(n.GetID());
		Node tmp = htNodes.Get(uid);
		if(tmp!=null){
			if(tmp.equals(n))
				return false;
			else{
				throw new DuplicateID("Node with ID " + n.GetID() + " already exists in the graph");
			}
		}
		try {
			htNodes.RegisterID(uid, n);
			return true;
		} catch (DuplicateID e) {
			/* this will never happen because we
			 * tried to Get the node with the UID
			 * of this node above...
			 */
			e.printStackTrace();
			return false;
		}
	}

	/**
	 * Moves a node to be parented elsewhere in the graph.  Useful
	 * for cut-paste operations.  nodeToBeMoved will be inserted as
	 * the positionAtParent-th child of nodeToBeNewParent. 
	 * 
	 * Should not be called in anything other than a GUI for STEP 
	 * programming.  This node is not smart about checking if the
	 * move is legal.  To be easy, maybe make sure that the node
	 * to be moved isn't a splice or LTE...   
	 * 
	 * @param nodeToBeMoved
	 * @param nodeToBeNewParent
	 * @param positionAtParent (indexed from 0) 0 would insert this
	 * node before the first child, positionAtParent.children.length
	 * would insert this node as the last child
	 */
	public void MoveNode(Node nodeToBeMoved, Node nodeToBeNewParent, int positionAtParent){
		// 1. update all parent nodes to no longer point to this child
		for (int i=0 ; i<nodeToBeMoved.parents.length ; i++) {
			Node nTmp = nodeToBeMoved.parents[i];
			// remove all parent references to this node 
			// (sketchy because parameter order matters a ton)
			for(int j=0;j<nTmp.children.length;j++){
				if(nTmp.children[j]==nodeToBeMoved){
					// resize the children to remove this element
					Node newnodes[] = new Node[nTmp.children.length - 1];
					System.arraycopy(nTmp.children, 0, newnodes, 0, j);
					System.arraycopy(nTmp.children, j+1, newnodes, j, newnodes.length - i);
					nTmp.children = newnodes;
					// not sure what happens to the for loop.  Test it?
				}
			}
			
			nodeToBeMoved.parents[i] = null;
		}
		
		// 2. update this node to have it's parent to be the node
		// specified.  doesn't work well if a node has two parents
		// (via splice or otherwise) so you should change the
		// parameter to be an array and copy that in instead
		Node newParents[] = new Node[1];
		newParents[0] = nodeToBeNewParent;
		nodeToBeMoved.parents = newParents;
		
		// 3. Make sure the parent's children list has this node
		// as an element at the position given
		Node newnodes[] = new Node[nodeToBeNewParent.children.length + 1];
		System.arraycopy(nodeToBeNewParent.children, 0, newnodes, 0, positionAtParent);
		newnodes[positionAtParent] = nodeToBeMoved;
		System.arraycopy(nodeToBeNewParent.children, positionAtParent, newnodes, positionAtParent+1, newnodes.length - positionAtParent);
		nodeToBeNewParent.children = newnodes;

	}
	
	/**
	 * Remove the reference to a node.  The node must already have been
	 * disconnected from its parents and children.  ID will be revoked
	 * when complete.
	 * 
	 * Do not call this with a handle from an iterator!;
	 * you will get a ConcurrentModificationException!
	 * Use iterator.Remove instead!!
	 */
	public void RemoveNode(Node n) {		
		//assert(n.parents.length == 0);
		//assert(n.children.length == 0);
		
		htNodes.RemoveID(new UID(n.GetID()));		
	}
	
	/** 
	 * Disconnect a node from it's neighbors and remove it
	 * from the graph.
	 * Do not call this with a handle from an iterator!;
	 * you will get a ConcurrentModificationException!
	 * Use iterator.Remove instead!!
	 * 
	 */
	public void RemoveNodeAndDisconnect(String nodeID){
		Node n = GetNode(nodeID);
		if(n==null){
			return;
		}
		n.cleanup();
		RemoveNode(n);
	}
	
	/**
	 * A Trivial graft merely adds @param gGraft heads to the this.graph.
	 * 
	 * Caller should have lock on <i>this<i>
	 *  
	 * @param gGraft
	 * 
	 */
	synchronized public void TrivialGraft(Graph gGraft){
		assert(isWriteLockedByCurrentThread());
		    	   	    	
    	/* First, build a list of "head" nodes.
		   These are the points we need to "Realize",
		   and to "Want" if the graph is live. */

    	gGraft.getReadLock();
    	
    	Node n = null;
		Iterator<Node> it = gGraft.GetNodeIterator();
        while (it.hasNext()) { 
        	n = it.next();

			/* Build the list of "heads" for realization/wanting/etc */
			if (n.IsOrphan()) {
				n.Realize(this);
			}
    	}
    	gGraft.releaseReadLock();
	}
			
    /**
     * This method will graph the specfied graph @param gGraft into the
     * current graph as per the rules outlined in the technical report.
     * Particularly, the "this" graph (the base) and the new incomming
     * graph (the Graft) shall be merged such that the graft is grafted
     * into the base.  We take action if the graft contains at least
     * one node that shares an ID with a node already in the graph.  This
     * node may either be a "SpliceNode" or a 'regular' Node.  How this
     * new graph is inserted into the base graph depends on the type of
     * this node.  
     * 
     * If there is no node with ID in common between both the base and the 
     * graft, the graft is "superficial" and the graft is actually added
     * as a completely independent graph within this graph 
     * 
     * If there is a splice node that can not be identified in the base
     * graph, a dangling splice is thrown. 
     * 
     * @param gGraft
     * @throws DanglingSplice
     * @throws ClassNotFoundException 
     */
    synchronized public void Graft(Graph gGraft) throws DanglingSplice, ClassNotFoundException{

		assert(!rwLock.isWriteLockedByCurrentThread());
		    	   	
    	/* iterate through the nodes in the to-be-appended ("graft") graph */
    	java.util.LinkedList<step.Node> heads = new java.util.LinkedList<step.Node>();
    	
    	/* First, build a list of "head" nodes.
		   These are the points we need to "Realize",
		   and to "Want" if the graph is live. */

    	gGraft.getReadLock();

    	Node n = null;
		Iterator<Node> it = gGraft.GetNodeIterator();
        while (it.hasNext()) { 
        	n = it.next();

    		/* Build the list of "heads" for realization/wanting/etc */
			if (n.IsOrphan()) {
				if (!(n instanceof SpliceNode)) {
					heads.add(n);
				}
			} else {
				
				/* TODO: mjo: I think adam had sockets in mind here,
				 * not splices.  Check this if it becomes an issue
				 * with nodes that have only splices/sockets as parents.
				 */
				boolean spliceParentsOnly = true;
				for (int i=0 ; i<n.parents.length ; i++) {
					if (!(n.parents[i] instanceof SpliceNode)) {
						spliceParentsOnly = false;
						break;
					}
				}
				if (spliceParentsOnly)
					heads.add(n);
			}
    	}
    	gGraft.releaseReadLock();
    	
    	assert(!rwLock.isWriteLockedByCurrentThread());

    	/**
    	 * TARGET check for graft.
    	 * Sanity check that ensures all targetted nodes
    	 * exist either in the new graph or the base 
    	 * graph (this encompases both Normalize
    	 * and Realize).  Worth doing as it will save us
    	 * terrible work trying to roll-back *after*
    	 * the graph has been merged.
    	 **/
    	
    	/**
    	 * get the lock and hold it.  We don't want the
    	 * graph to change once we assume we're all clear
    	 */
    	
    	getWriteLock();
    	String sTarget = null;
    	boolean bTargetFailure = false;
    	
    	it = gGraft.GetNodeIterator();
        while (it.hasNext()) { 
        	n = it.next();

    		sTarget = null;
    		if(n instanceof SpliceNode){
    			 sTarget = ((SpliceNode) n).GetTarget();
    		}
    		else if(n instanceof LastTriggerEval){
   			 	sTarget = ((LastTriggerEval) n).GetTarget();
    		}
    		if(sTarget!=null){
    			Node nTarget = gGraft.GetNode(sTarget);
    			if(nTarget==null)
    				nTarget = this.GetNode(sTarget);
    			
    			if(nTarget==null){
    				// target node DNE... bail.
    				bTargetFailure = true;
    				break;
    			}
    		}
    	}
    	if(bTargetFailure){
    		releaseWriteLock();
    		throw new DanglingSplice(gGraft,(ReferenceNode)n);
    	}
    	
    	//make sure bindings are OK before admission
    	
    		try {
				gGraft.Bind();
			} catch (ClassNotFoundException e) {
				releaseWriteLock();
				throw e;
			}
    	
    	
    	/* end TARGET check */    	
    	

    	it = gGraft.GetNodeIterator();
        while (it.hasNext()) { 
        	n = it.next();

			n.SourceGraphID = gGraft.ID;
	    	if (n instanceof SpliceNode) {
	    		/* mjo: added 1/29/06 -- if the splice node
	    		 * specifies a target in the new graph (and
	    		 * the target hasn't been added yet) add it
	    		 * prematurely to avoid an incorrect miss.
	    		 */
	    		sTarget = ((SpliceNode) n).GetTarget();

	    		// if the target node hasn't been added yet
	    		// make sure we add it early.
	    		if(this.GetNode(sTarget)==null){
	    			Node nTmp = gGraft.GetNode(sTarget); 
	    			if(nTmp!=null){
	    				try {
							AddNode(nTmp);
						} catch (DuplicateID e) {
							// this won't happen b/c we tried to get
							// it from above.
							e.printStackTrace();
							assert(false);
						}
	    			}
	    			else {
	    				releaseWriteLock();
	    				throw new DanglingSplice(this,(ReferenceNode)n);
	    			}	
	    		}
	    		/* FIXME: this looks wrong...
	    		 * In the active graph, replace the argument with
	    		 * its target.
	    		 */ 
	    		ResolveSplice((SpliceNode) n);
	    		it.remove();
	    	} else if (GetNode(n.GetID()) != null) {
	    		/* The node is not a splice & therefore needs to replace the
	    		 * node in the existing graph */
	    		Node nDoppelganger = (Node)n;
	    		Node nTarget = GetNode(nDoppelganger.GetID());
	    		if(nTarget!=null){					
					/* reparent our new node (the doppleganger) into the tree */
					nTarget.graft_RedirectParentsToNode(nDoppelganger);
					/* If a doppelganger has no children, we take the children
					 * of the old node, else the old children become orphaned
					 */
					if(nDoppelganger.children.length==0){
						nTarget.graft_RedirectChildrenToNode(nDoppelganger);
					} else {
						/* abandon existing children in the graph -- i.e., do
						 * nothing (don't explicitly add them).  Nor should we 
						 * mark children as garbage!  They may be linked to elsewhere */
					}
					
					/* Remove the old node */
					RemoveNode(nTarget);
					
					/* add this node to the base */
					try {
						AddNode(nDoppelganger);
					} catch (DuplicateID e) {
						/* Guarenteed not to happen, since we removed the node of the
						 * same ID above. */
						e.printStackTrace();
						assert(false);
					}

	    		} else {
					/* otherwise, the node is brand spanking new and 
					 * requires no grafting magic */
				}
			}
		}
		assert(rwLock.isWriteLockedByCurrentThread());

		it = heads.iterator();
		while (it.hasNext()) {
			Node head = (Node) it.next();
			head.Realize(this);
			if (bound) 
				try {
					head.SetWanted(true); /* DOME - this should not propogate across sockets. */
				} catch (EvaluationFailure ex) {
					/* no-op */
				}
		}
		
		try{
			if (normalized)
				Normalize();
			if (bound)
				Bind();
		}
		catch(Exception ex){
				/* this graph is now hosed since 
				 * the new nodes have been added
				 * would have been better to check 
				 * for such failures before
				 **/
				
			}
		
		System.out.println("graft complete");
		if(bAsleep){
			System.out.println("graft noticed iterator:asleep!  Waking...");
			notify();
		}
		
		releaseWriteLock();
		assert(!rwLock.isWriteLockedByCurrentThread());
	}
	
	/** 
	 * iterate through the nodes that belong to the graph and remove 
	 * nodes that have been marked as garbage.  These are nodes that
	 * have become disconnected or otherwise unloved as a result of 
	 * a "graft" or "prune" call.
	 * 
	 * This should be run periodically and called only by NodeJanitor

	 * concurrentModificationExceptions between the nodes iterator
	 * and the modification are avoided by building a "workList" that
	 * is processed after iteration.
	 * 
	 */
	public ArrayList<String> cleanup(){
		assert(rwLock.isWriteLockedByCurrentThread());
		
		ArrayList<String> prunedNodes = new ArrayList<String>();
		
		Node n = null;
		Iterator<Node> it = htNodes.Values().iterator();
        while (it.hasNext()) { 
        	n = it.next();
		
			if(n.checkExpired()){
				Log.janitor.log("EXPIRED : " + n.ID + " -begining cleanup phase.",
						Trace.MINIMAL);
				
				prunedNodes.add(n.ID);
			}
		}
        
        for(String s:prunedNodes){
			/* clean up the node */
			n = GetNode(s);
        	n.cleanup();
			/* remove from nodes list */
			RemoveNode(n);
        }
				
		return prunedNodes;
	}
	
	public ArrayList<Node> GetAllAncestors(Node n){
		Map<String,Node> m = n.GetAllAncestorsCycleSafe();
		
		return new ArrayList<Node>(m.values());
	}
	
	/** 
	 * Mark this node as garbage, as well as it's parents 
	 *  (nodes that depend on it for computation)
	 *  increment local needs as a result of deletion
	 *  
	 *  caller takes responsibility for synch!
	 *  
	 * @param n
	 */
	public void markForDeletion(Node n) {
		//assert(rwLock.isWriteLockedByCurrentThread());
		
		assert(GetNode(n.ID) == n);
		if(!n.isGarbage()){
			n.markAsGarbage();
			SxeMonitor.incrAvailableResources(n.getCost());
		}
		for(int i=0;i<n.parents.length;i++){
			markForDeletion(n.parents[i]);
		}
	}
	
	/**
	 * Never Used... 
	 * Mark this node as garbage, as well as it's parents 
	 *  (nodes that depend on it for computation)
	 * @param ID
	 
	private void prune(String ID) throws Exception{	
		Node n = GetNode(ID);
		if(n!=null){
			getWriteLock();
			prune(n);
			releaseWriteLock();
		}
		else
			throw new Exception("Node to be pruned could not be found");
	}
	*/
	
	/**
	 * returns nodes that don't have parents
	 */
	public Node[] getRoots(){
		getReadLock();
		Node n = null;
		ArrayList<Node> al = new ArrayList<Node>();
		
		
		Iterator<Node> it = this.GetNodeIterator();
        while (it.hasNext()) { 
        	n = it.next();

			if(n.IsOrphan()){
				/* add this node */
				al.add(n);
			}
		}
		releaseReadLock();
		// SJJ - SMOD: Fixed this casting that was causing problems 
		return al.toArray(new Node[] {});
	}

	/**
	 * returns nodes that don't have any children 
	 * (or are LTE)
	 */
	public ArrayList<Node> getLeaves(){
		getReadLock();
		Node n = null;
		
		ArrayList<Node> al = new ArrayList<Node>();
		
		Iterator<Node> it = this.GetNodeIterator();
        while (it.hasNext()) { 
        	n = it.next();

        	if(n.children.length == 0){
				/* add this node */
				al.add(n);
			}
			else if(n instanceof LastTriggerEval)
			{
				/* add this node too */
				al.add(n);
			}
		}
		releaseReadLock();
 
		return al;
	}
	
	public String GetID() { return ID; }
	public void SetID(String sID){ ID = sID; }
	
	
	public boolean isWriteLockedByCurrentThread(){
		//System.out.println(rwLock.toString());
		return rwLock.isWriteLockedByCurrentThread();
	}
	
	public void getWriteLock() {
		// EFFECTS:
		//     Tries to adquire the write lock in this, blocking
		//     if necessary until the lock becomes available.
		if (rwLock.isWriteLockedByCurrentThread()) return;
		rwLock.writeLock().lock();
	}
	
	public void getReadLock() {
		// EFFECTS:
		//     Adquire the read lock in this graph, blocking
		//     if necessary until the lock becomes available.
		rwLock.readLock().lock();
	}
	
	public void releaseWriteLock() {
		// EFFECTS:
		//     Release write lock on this graph
		rwLock.writeLock().unlock();
	}
	
	public void releaseReadLock() {
		// EFFECTS:
		//     Release read lock on this graph
		rwLock.readLock().unlock();
	}

	/**
	 * Used by Service Dispatcher to create seperate Graphs
	 * from the single graph received.  Also inserts sockets 
	 * into the graph where needed
	 * 
	 * @param gToSplit
	 * @throws URISyntaxException 
	 * @throws DuplicateID 
	 */
	 public static Map<String,Graph> graphSplitter(Graph gToSplit) throws URISyntaxException, DuplicateID{
		LinkedList<Node> workQueue = new LinkedList<Node>();
		
		/* map of SXE ID's and the graphs they will get */
		Map<String,Graph> newGraphs = new HashMap<String,Graph>();
		
		/* maintain a list of nodes we've visited and the SXE
		 * the nodes have been added to */
		Map<String,String> visited = new HashMap<String,String>();
	
		int i=0;
			
    	for(Node n:gToSplit.getRoots()){
    		if(visited.containsKey(n.GetID())){
    			continue;
    		}
    		workQueue.add(n);
			visited.put(n.GetID(),n.getBindTo());
			Graph g = null;
		
			//	get or create the temp graph for this node's SXE binding
			g = newGraphs.get(n.getBindTo());
			if(g==null){
				g = new Graph(gToSplit.GetID() + ":" + String.valueOf(i));
				newGraphs.put(n.getBindTo(), g);
				i++;
			}

			Node parent = n;
			while(!workQueue.isEmpty()){
				Node p = workQueue.remove();
	
				g.AddNode(p);
				//parent.AddChild(p);
				parent = p;
		
				if(!parent.getBindTo().equals(p.getBindTo())){
					System.err.println("Internal error with bindings.  Nodes are connected despite seperate bindings.\n" +
							"Nodes in question are " + parent.GetID() + " bound to " + parent.getBindTo() + " and " + 
							p.getBindTo() + " bound to " + p.getBindTo());
					return null;
				}
				
				// process children
				for(Node t:p.getChildren()){
					if(!visited.containsKey(t.GetID())){
						visited.put(t.GetID(),t.getBindTo());
						workQueue.add(t);
					}
				}
			}
    	} /* end for(roots)*/
    	
    	System.out.println("Made " + newGraphs.size() + " graphs.  They are:");
    	int f = 0;
    	for(Graph gX:newGraphs.values()){
    		System.out.println("--GRAPH " + f + "--");
    		System.out.println(gX.Serialize());
    		f++;
    	}
    	return newGraphs;
	 }
	 
	 protected static void socketInsertion(Graph gToProc) throws URISyntaxException, DuplicateID{			
		 // iterate over a copy of the node list as it will change while we process it.

		 ArrayList<Node> tba = new ArrayList<Node>();
		 
		 Node p = null;
		 Iterator<Node> it = gToProc.GetNodeIterator();
	     while (it.hasNext()) { 
	    	 p = it.next();
 
			// process children of all nodes
			for(Node t:p.getChildren()){
				// these nodes are bound to different SXEs.  
				// insert socket nodes
				if(!p.getBindTo().equals(t.getBindTo())
					&&(!((p instanceof SocketNode)&&(t instanceof SocketNode))))
				{
					// 1. create socket nodes
					UID newIDr = gToProc.htNodes.RequestNextID("autoRecvSocket" + p.GetID() + "to" + t.GetID());
					UID newIDs = gToProc.htNodes.RequestNextID("autoSendSocket" + t.GetID() + "to" + p.GetID());
					
					System.out.println("Adding sockets {" + newIDr.get() + "/" + newIDs.get() + "} between nodes p=[" + p.GetID() + "] and t=[" + t.GetID() + "]");
					
					ReceiverUdpSocketNode rsn = 
						new ReceiverUdpSocketNode(newIDr.get(),newIDs.get(),new URI(p.getBindTo()));
												
					SenderUdpSocketNode ssn = 
						new SenderUdpSocketNode(newIDs.get(),rsn.GetID(),new URI(t.getBindTo()));
				
					// 2. insert into graph later (add to tba now)		
					tba.add(rsn);
					tba.add(ssn);
					
					for(int j=0;j<p.children.length;j++){
						if(p.children[j]==t){
							p.children[j] = rsn;
						}
					}

					for(int j=0;j<t.parents.length;j++){
						if(t.parents[j]==p){
							t.parents[j] = ssn;
						}
					}
					
					rsn.AddParent(p);
					ssn.AddChild(t);
					
					// fix continuity for printing
					// rsn.AddChild(ssn);
					// ssn.AddParent(rsn);
					
					// 3. set bindings and add to BFS
					rsn.bindTo = p.getBindTo();
					ssn.bindTo = t.getBindTo();	
				}
			}
	     }
	     for(Node n:tba){
			gToProc.AddNode(n);
	     }
	 }
	 
	 public static void main(String[] args) {
		step.Graph g = null;
		String sBindTo = null;
		int iFakeSXEs = 0;
		
		System.err.println("Graph Splitter Tester");
		
		if ((args.length <1) && (args.length > 2)) { 
			System.err.println("run two ways one arg is the STEP graph to be split.  If bindTo not set " +
					"for every node in the graph this _will_ fail.");
			System.err.println("Two args: arg1=STEP graph to be split.  arg2=#fake SXEs to bind with");
			return;
		}
		
		if(args.length==2){
			iFakeSXEs = Integer.parseInt(args[1]);
			System.out.println("will generate SXE names for every unspecified node with values from SXE1 to SXE" + iFakeSXEs);
		}
		
		g = step.parse.Parser.Parse(new java.io.File(args[0]),false);
		if(g==null)
			System.exit(-1);
		
		try {
			g.Normalize();
		} catch (DanglingSplice e1) {
			e1.printStackTrace();
			System.exit(-1);
		}
		
		/* graphical rendering */		
		JFrame jf = new JFrame("STEP Viewer");
		jf.setPreferredSize(new Dimension(300,400));
		JTabbedPane jtp = new JTabbedPane();
		jf.add(jtp);
		jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		jf.pack();	
		jf.setVisible(true);			
		

		/* Randomized bindTo assignments */
		Random r = new Random();
		Node n = null;
		Iterator<Node> it = g.GetNodeIterator();
		while(it.hasNext()){
			n = it.next();
			if(n.getBindTo().equals("")){
				if(iFakeSXEs == 0){
					System.out.println("bindTo must be set for every node in the graph.  No binding for [" + n.GetID() + "]");
					System.exit(-1);
				}
				else{
					sBindTo = "SXE" + String.valueOf(r.nextInt(iFakeSXEs) + 1);
					n.bindTo = sBindTo;
				}
			}
		}
		
		System.out.println("--------------------INPUT FILE---------------------");
		System.out.println(g.Serialize());
		//g.WriteDotFile("splitter-before.dot");
		jtp.insertTab("original", null,new JStepPanel(g,JStepPanel.ColorMode.BINDING) , "the original graph", 0);
		try {
			System.out.println("Inserting Sockets...");			
			Graph.socketInsertion(g);
			jtp.insertTab("socketted", null, new JStepPanel(g,JStepPanel.ColorMode.BINDING) , "the socketted graph 1", 1);
			System.out.println("DONE Inserting Sockets.");
			System.out.println("--------------------SOCKETTED FILE---------------------");
			//g.ReplaceSplices();
			//jtp.insertTab("socketted2", null, new JStepPanel(g,JStepPanel.ColorMode.BINDING) , "the socketted graph 2", 1);
			System.out.println(g.Serialize());
			System.out.println("Splitting graphs");
						
			Map<String,Graph> msg = Graph.graphSplitter(g);
			System.out.println("DONE Splitting graphs");
			System.out.println("--------------------FINAL GRAPH---------------------");
			
			int i = 1;
			for(String s : msg.keySet()){
				Graph grSplit = msg.get(s);
				jtp.insertTab("final part " + i, null, new JStepPanel(grSplit,JStepPanel.ColorMode.BINDING) , "the final graph " + i , 1 + i);
				//grSplit.WriteDotFile(i + "splitter-after.dot");
				i++;
			}
		} catch (URISyntaxException e) {
			e.printStackTrace();
		} catch (DuplicateID e) {
			e.printStackTrace();
		}
	 }
	 		
		public static int ComputeNeeds(Graph g) {
			// TODO: mjo: actually compute the needs of the given node
			int t = 0;
			
			Node n = null;
			Iterator<Node> it = g.GetNodeIterator();
			while(it.hasNext()){
				n = it.next();
				
				//if(n instanceof ExpNode)
				t+=n.getCost();
			}
			return t;
		}

		
		
		/*****************************************************************************************
		 * Load a STEP graph from the file specified.
		 * 
		 * @param sFileName - the file name that contains the XML for the STEP graph requested
		 * @param bResolveSplices - resolve the splices (splice nodes) in the graph?
		 * @return - the STEP graph, or null on failure.
		 */
		static public step.Graph LoadGraphFromFile(String sFileName, boolean bResolveSplices){
			Graph stepg = null;
			java.io.File f = new java.io.File(sFileName);
	    	
			if(!f.exists()){
				System.err.println("STEP file '" + f.getName() + "' does not exist.");
				return null;
			}
					
			System.out.println("Parsing STEP file '" + f.getName() + "'.");
			stepg = step.parse.Parser.Parse(f,false);
			System.out.println("Parsed STEP file '" + f.getName() + "'.");		

			if(bResolveSplices)
				try{
					System.out.println("Resolving splices for STEP file '" + f.getName() + "'.");						
					// don't resolve splices for this!!
					stepg.ResolveSplices();
					System.out.println("Resolved splices for STEP file '" + f.getName() + "'.");		
				}catch(Exception e)
				{ 
					e.printStackTrace(); 
					return null;
				}
			return stepg;
		}

		/**
		 * produces a valid UUID based on the prefix given
		 * 
		 * @param Prefix
		 * @return
		 */
		public String ProduceID(String Prefix) {
			return htNodes.RequestNextID(Prefix).get();
		}

}

